package com.data.algorithm.sort;

/**
 * 希尔排序
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/3/7
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[8000000];

        for (int i = 0; i < 8000000; ++i) {
            arr[i] = (int) (Math.random() * 80000000.0D);
        }
        int[] arr2 = arr.clone();

        Long startTime = System.currentTimeMillis();
        System.out.println("开始排序");
        shellSort2(arr);
        Long endTime = System.currentTimeMillis() - startTime;

        System.out.println("排序耗时：" + endTime + "毫秒");
        System.out.println("排序耗时：" + endTime / 1000 + "秒");

        Long startTime1 = System.currentTimeMillis();
        System.out.println("开始排序");
        shellSort3(arr2);
        Long endTime1 = System.currentTimeMillis() - startTime1;

        System.out.println("排序耗时：" + endTime1 + "毫秒");
        System.out.println("排序耗时：" + endTime1 / 1000 + "秒");
    }

    /**
     * 替换法希尔排序，效率不高
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int temp = 0;
        for(int gap = arr.length / 2; gap > 0; gap /= 2) {
            for(int i = gap; i < arr.length; ++i) {
                for(int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }


    /**
     * 移位法希尔排序
     * @param arr
     */
    public static void shellSort2(int[] arr) {

        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; ++i) {
                int j = i;
                int temp = arr[i];
                if (arr[i] < arr[i - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }

            }
        }
    }

    /**
     * 移位法希尔排序2
     * @param arr
     */
    public static void shellSort3(int[] arr) {

        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; ++i) {
                int temp = arr[i];
                int insertIndex;
                for(insertIndex = i - gap; insertIndex >= 0 && temp < arr[insertIndex]; insertIndex -= gap) {
                    arr[insertIndex + gap] = arr[insertIndex];
                }
                if (insertIndex + gap != i) {
                    arr[insertIndex + gap] = temp;
                }
            }
        }
    }
}